package org.zdw.data.structure.select;

import java.util.ArrayList;
import java.util.List;

public class CreateTreeByArray<E> {

    public static class Node<E>{
        Node<E> left = null;  //左子树
        Node<E> right = null; //右子树
        E data = null;          //数据域

        //初始化节点
        public Node(E data){
            this.data = data;
            this.left = null;
            this.right = null;
        }

        public Node(){

        }
    }

    private Node<E> root = null;

    private List<Node<E>> list = null; //节点列表，用于将数组元素转化为节点

    public Node<E> getRoot(){
        return this.root;
    }

    public void createTreeByArray(E[] array){
        this.list = new ArrayList<Node<E>>();
        for (int i = 0;i< array.length;i++){
            list.add(new Node<E>(array[i]));
        }

        System.out.println("头节点->" + list.get(0).data);
        this.root = new Node<E>(list.get(0).data); //根节点

        for(int j = 0; j < (list.size() / 2); j ++){
            try {
                list.get(j).left = list.get(j * 2 + 1);
                System.out.println("节点" + list.get(j).data + "左子树 ->" + list.get(j * 2 + 1).data);
                list.get(j).right = list.get(j * 2 + 2);
                System.out.println("节点" + list.get(j).data + "右子树 ->" + list.get(j * 2 + 2).data);
            }catch (Exception e){

            }
        }
    }

    /**
     * 先遍历二叉树
     * @param root
     */
    public void Indorder(Node<E> root){
        if(root == null){
            return;
        }
        System.out.println(root.data);
        Indorder(root.left);
        Indorder(root.right);
    }

    /**
     * 中遍历二叉树
     * @param root
     */
    public void inOrderTraverse(Node<E> root){
        if(root == null){
            return;
        }
        inOrderTraverse(root.left);
        System.out.println(root.data);
        inOrderTraverse(root.right);
    }

    public void postOrderTraverse(Node<E> root){
        if(root == null){
            return;
        }
        Indorder(root.left);
        Indorder(root.right);
        System.out.println(root.data);
    }

    public static void main(String[] args) {
        CreateTreeByArray<Integer> createTreeByArray = new CreateTreeByArray<Integer>();
        Integer[] arrays = {1,2,3,4,5,6,7,8,9,10};
        createTreeByArray.createTreeByArray(arrays);
        System.out.println("===============================");
        createTreeByArray.inOrderTraverse(createTreeByArray.list.get(0));
    }
}
